The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.
The Newton algorithm and its variants, notably Iteratively Reweighted Least Squares (IRLS), are algorithms of choice to solve logistic regression models. IRLS often requires a small number of iterations to converge compared to alternative techniques, such as Broyden-Flecher-Goldfarb-Shanno (BFGS), Alternating Direction Method of Multipliers (ADMM), or nonlinear conjugate gradient descent. Newton algorithms in general and IRLS in particular rely upon the efficient calculation of the Hessian matrix: H=XT AX, where XεIRm×n is the input data, and AεIRm×m is a diagonal matrix. Computing H (also known as the “cross product”) and its Cholesky factors are generally the most time consuming steps of the Newton algorithm and its variants.
In many cases, an exact Hessian matrix is not required for the algorithm to eventually converge, any “sufficiently close” symmetric positive-definite approximation will yield reasonable performance, but may require the algorithm to iterate more times than if the exact Hessian were used. In addition, Hessian approximations can be effectively used as preconditions for other techniques, such as Trust Region Newton and Preconditioned Conjugate Gradient frameworks.